//https://leetcode.cn/problems/sort-the-matrix-diagonally/description/?envType=daily-question&envId=2024-04-29

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; ++i) {
            vector<int> temp;
            for (int x = i, y = 0; x < m && y < n; ++x, ++y) {
                temp.push_back(grid[x][y]);
            }
            ranges::sort(temp);
            for (int x = i, y = 0; x < m && y < n; ++x, ++y) {
                grid[x][y] = temp[y];
            }
        }

        for (int i = 0; i < n; ++i) {
            vector<int> temp;
            for (int x = 0, y = i; x < m && y < n; ++x, ++y) {
                temp.push_back(grid[x][y]);
            }
            ranges::sort(temp);
            for (int x = 0, y = i; x < m && y < n; ++x, ++y) {
                grid[x][y] = temp[x];
            }
        }

        return grid;
    }
};